ICPC Live Archive/3928 - Ballroom lights/help/gomox.ar-pap-2010-d9b17e5cb110/tpc/new-distinct-substrings/main.cpp

   1 #include <string.h>
   2 #include <cstdio>
   3 #include <algorithm>
   4
   5 using std::sort;
   6 using std::swap;
   7
   8 static char text[50001];
   9 static unsigned int sa[50000];
  10 static unsigned int rank1[50000]={0};
  11 static unsigned int rank2[50000]={0};
  12
  13 static int N;
  14 static long long total;
  15 static unsigned cuantos;
  16
  17 bool parar;
  18 int bucket, aux, desde, actual;
  19 unsigned int* ahora;
  20 unsigned int* proximo;
  21
  22
  23 // Comparador
  24 struct Comparador {
  25     const int K;
  26     const unsigned int* rank;
  27     Comparador(const int j,const unsigned int* vrank): K(j), rank(vrank) {};
  28
  29     bool inline operator()(const int i, const int j) const {
  30         return clave(i) < clave(j);
  31     }
  32
  33     int inline clave(const int i) const {
  34         return (i+K < N ? rank[i+K]+1 : 0);
  35     }
  36 };
  37
  38
  39 int main(int argc, const char *argv[]) {
  40
  41     scanf("%d", &cuantos);
  42
  43     for (int c = 0; c < cuantos; c++) {
  44
  45         scanf("%s", text);
  46         N = strlen(text);
  47
  48         // Suffix Array
  49         for (int i = 0; i < N; i++) {
  50             sa[i] = i;
  51             rank1[i] = text[i];
  52         }
  53
  54
  55         sort(sa, sa+N, Comparador(0, rank1));
  56
  57         bucket = 0;
  58         rank1[sa[0]] = 0;
  59
  60         for (int t = 1; t < N; t++) {
  61             if (text[sa[t-1]] == text[sa[t]]) {
  62                 rank1[sa[t]] = bucket;
  63             } else {
  64                 bucket = t;
  65                 rank1[sa[t]] = bucket;
  66             }
  67         }
  68
  69         parar = true;
  70         ahora = rank1;
  71         proximo = rank2;
  72
  73         for (int K = 1; K < N; K *= 2) {
  74             desde = 0;
  75             actual = 1;
  76             Comparador comparador(K,ahora);
  77             while (actual < N) {
  78                 while (actual< N && ahora[sa[actual]] == ahora[sa[actual-1]]) {
  79                     actual++;
  80                 }
  81                 if (actual > desde+1) {
  82                     sort(sa+desde, sa+actual, comparador);
  83                 }
  84                 desde = actual;
  85                 actual++;
  86             }
  87
  88             bucket = 0;
  89             proximo[sa[0]] = 0;
  90             aux = 0;
  91
  92             for (int t = 1; t < N; t++) {
  93                 if (ahora[sa[t]] == aux && comparador.clave(sa[t-1]) == comparador.clave(sa[t])) {
  94                     proximo[sa[t]] = bucket;
  95                     parar = false;
  96                 } else {
  97                     aux = ahora[sa[t]];
  98                     bucket = t;
  99                     proximo[sa[t]] = bucket;
 100                 }
 101             }
 102
 103             swap(ahora, proximo);
 104             if (parar) break;
 105             parar = true;
 106         }
 107
 108         // LCP (Kasai)
 109         total = 0;
 110         int k = 0;
 111         for (int i = 0; i < N; i++) {
 112             if (k > 0) {
 113                 k--;
 114             }
 115             if (ahora[i] == N-1) {
 116                 total += N + 1 - sa[N-1];
 117                 k = 0;
 118                 continue;
 119             }
 120             int j = sa[ahora[i]+1];
 121             while (text[i+k] == text[j+k]) k++;
 122             total += N - k - sa[ahora[i]];
 123         }
 124
 125         // El codigo de arriba pone un -1 en la
 126         // fila final del LCP en lugar de un 0 en la primera,
 127         // asi que hay que restarlo ahora.
 128         total = total - 1;
 129
 130         printf("%lld\n", total);
 131     }
 132 }